package leetcode_动态规划._07背包问题.完全背包;

import java.util.Arrays;

/**
 * @author yzh
 * @data 2021/3/20 12:36
 * 零钱兑换
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
 * 如果没有任何一种硬币组合能组成总金额，返回 -1
 * 思路：
 *   dp[i] = min(dp[i - nums[j]] + 1, dp[i]);
 */
public class _322 {

    // 先遍历背包，再遍历物品
    public int coinChange_1(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j] && dp[i - coins[j]] != Integer.MAX_VALUE)
                    dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) return -1;
        return dp[amount];
    }

    // 先遍历物品，再遍历背包；耗时和内存都比第一个的好
    public int coinChange_2(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != amount + 1)
                    dp[j] = Math.min(dp[j], dp[j - coins[i]]);
            }
        }
        if (dp[amount] == amount + 1) return -1;
        return dp[amount];
    }
}
